length -> endpoints
-------------------
1 -> 1 0
1 -> 19 18
1 -> 20 19
2 -> 6 4
2 -> 20 18
3 -> 4 1
4 -> 4 0
5 -> 6 1
5 -> 11 6
6 -> 6 0
7 -> 11 4
7 -> 18 11
8 -> 19 11
9 -> 20 11
10 -> 11 1
11 -> 11 0
12 -> 18 6
13 -> 19 6
14 -> 18 4
14 -> 20 6
15 -> 19 4
16 -> 20 4
17 -> 18 1
18 -> 18 0
18 -> 19 1
19 -> 19 0
19 -> 20 1
20 -> 20 0The Saint-Exupéry Ruler
puzzle
modeling
Problem description
Perfection is achieved not when there is nothing more to add, but when there is nothing left to take away.
— Antoine de Saint-Exupéry
The problem is to design a ruler of \(n\) units using the fewest possible graduations, such that all possible integer lengths appear on the ruler. This puzzle was published by Mickaël Launay (Launay 2025). An example with \(n=6\) is displayed in the Figure below:
Length \(1\) can be measured with marks \(0\) and \(1\), length \(2\) with marks \(4\) and \(6\), length \(3\) with marks \(1\) and \(4\), length \(4\) with marks \(0\) and \(4\), length \(5\) with marks \(6\) and \(1\), and length \(6\) with marks \(0\) and \(6\).
MIP model
Parameters
- \(N = \{0,1,\dots,n\}\): set of units of the ruler
Variables
- \(\textcolor{blue}{x}_i \in \{0,1\}\): takes value \(1\) if and only if there is a mark on unit \(i\in N\)
- \(\textcolor{blue}{y}_{i,j} \in \{0,1\}\): takes value \(1\) if and only if there are marks on units \(i\in N\) and \(j\in N\), \(i< j\)
Objective function
The problem is to minimize the number of marks:
\[ \min \sum_{i \in N} \textcolor{blue}{x}_i \]
subject to:
Constraints
- All possible integer lengths must appear somehow on the ruler:
\[ \sum_{i<j, \;j-i=k} \textcolor{blue}{y}_{i,j} \ge 1 \quad \forall k \in N, k>0 \tag{1} \]
- Variables \(\textcolor{blue}{x}_i\) and \(\textcolor{blue}{y}_{i,j}\) must be consistent:
\[\begin{align} \textcolor{blue}{y}_{i,j} &\le \textcolor{blue}{x}_i &\forall i<j \tag{2}\\ \textcolor{blue}{y}_{i,j} &\le \textcolor{blue}{x}_j &\forall i<j \tag{3}\\ \textcolor{blue}{x}_i+\textcolor{blue}{x}_j &\le \textcolor{blue}{y}_{i,j}+1 &\forall i<j \tag{4} \\ \end{align}\]
Constraints \((2)\) and \((3)\) enforce \(\textcolor{blue}{y}_{i,j}=1\implies \textcolor{blue}{x}_i=1\) and \(\textcolor{blue}{x}_j=1\), constraints \((4)\) enforce the reciprocal relationship.
Solution
Solving this problem with \(n=20\) takes less than a second with the default solver in PuLP (CBC) and yields:
So the 20 unit ruler can be designed with \(8\) marks. We can check that all integer lengths do appear on the ruler (some lengths appear multiple times):
References
Launay, Mickaël. 2025. “La Règle Saint-Exupérienne : L’énigme Maths Du Monde n°82.” 2025. https://www.lemonde.fr/sciences/article/2025/12/20/la-regle-saint-exuperienne-l-enigme-maths-du-monde-n-82_6658931_1650684.html.